package model;

/**
 * This class has methods for solving the coin game using a slow recursive algorithm.
 * 
 * @author Karen Berntsen (s0815799)
 * @author Erik Stens (s0615374)
 */
public class CoinGameSolverRecursive implements CoinGameSolver {
	private int[]	coins;
	
	public CoinGameSolverRecursive(int[] coins) {
		this.coins = coins;
	}
	
	/**
	 * Solving algorithm. Makes use of recursion to find the best solution for the game.
	 * 
	 * @return the minimum value the first player should at least be able to get
	 */
	@Override
	public int solve() {
		return maximumValue(0, coins.length - 1);
	}
	
	/**
	 * Calculates the minimum value player 1 can at least get, given that it's player 1's turn.
	 * 
	 * @param l
	 *            the left limit of the subset of consecutive coins that is being looked at in this part of the recursion
	 * @param r
	 *            the right limit of the subset of consecutive coins that is being looked at in this part of the recursion
	 * @return the minimum value player 1 should at least be able to get
	 */
	private int maximumValue(int l, int r) {
		if (l == r) {
			return coins[l];
		}
		return Math.max(maximumValue2(l + 1, r) + coins[l], maximumValue2(l, r - 1) + coins[r]);
	}
	
	/**
	 * Calculates the minimum value player 1 can at least get, given that it's player 2's turn.
	 * 
	 * @param l
	 *            the left limit of the subset of consecutive coins that is being looked at in this part of the recursion
	 * @param r
	 *            the right limit of the subset of consecutive coins that is being looked at in this part of the recursion
	 * @return the minimum value player 1 should at least be able to get
	 */
	private int maximumValue2(int l, int r) {
		if (l == r) {
			return 0;
		}
		return Math.min(maximumValue(l + 1, r), maximumValue(l, r - 1)); // minimum of the two choices, because by minimizing player 1's maximumValue, player 2 maximizes his/her own result.
	}
}
